Preliminary results

All the problems are in minimization here, i.e. if an objective function \(z(x)\) is actually in maximisation, we will minimise \(-z(x)\) instead. Only binary variables are considered here.

1 Instances

[An explanation of instances and instance names (as in the ReadMe file)]

List of test instances.

Go to instance example

Several methods for generating the coefficient of the objective functions are tested here. This is given by the column coef.

• random : the coefficient are generated randomly in the inerval [a,b]
• spheredown : the coefficient are generated on the non-dominated part of a sphere in minimisation in the interval [a,b]
• sphereup : the coefficient are generated on the non-dominated part of a sphere in maximisation in the interval [a,b]
• 2box : the coefficients are generated randomly in two small boxes of R^3

2 Input and output statistics

A set of statistics are stored for each instance and algorithm run.

2.1 Input statistics

For each instance we have the following statistics:

• Problem class (PC):
  • KP = Knapsack Problem
  • AP = Assignment Problem
  • UFLP = Uncapacited Facility Location Problem
• \(n\): number of variables.
• \(p\): number of objectives.
• rangeC: the range the objective coefficients are generated within
• coef: the method used for the generation of the objective coefficients (see section Research questions). We have:
  • random = random coefficient generation
  • 2box = two-boxes generation
  • spheredown = generation on the lower part of a sphere (in minimisation)
  • sphereup = generation on the upper part of a sphere (in minimisation)
• ratioND = proportion of objective coefficient vectors (here considered as a vector in \(\mathbb{R}^p\), one for each variable, defining the objective coefficient for all the objective for this variable) that are non-dominated (with respect to the other objective coefficient vectors).

2.2 Output statistics

For each algorithm run we have the following statistics, that can be found in stat,csv. Some of these are also input statistics but reintroduced as output statistics for a better readability. We have:

• pb: class of the problem.
• \(n\): number of variables.
• \(p\): number of objectives.
• coef: method for generation of the objective coefficients (see Section Research questions).
• rangemin: minimum possible value for the objective coefficients.
• rangemax: maximum possible value for the objective coefficients.
• nodesel: node selection strategy.
• varsel: variable selection strategy.
• OB: objective branching strategy.
• solved: 1 if the instance is solved within 3600 sec, 0 otherwise.
• YN: size of YN. If solved = 0, it represent the size of the upper bound set at 3600 sec, when the algorithm stops.
• nbnodes: number of nodes explored.
• mindepthT: minimal depth of a leaf node.
• maxdepthT: maximal depth of a leaf node (and thus of the tree).
• avgdepthT: average depth of the leaf nodes.
• avgdepthYN: average depth of the nodes where the non-dominated points were found.
• nbleaf: number of leaf nodes.
• nbinfeas: number of nodes pruned by infeasibility.
• pctinfeas: proportion (in %) of leaf nodes pruned by infeasibility.
• tpsinfeas: average time spend to prune a node by infeasibility (in msec).
• nbopt: number of nodes pruned by optimality.
• pctopt: proportion (in %) of leaf nodes pruned by optimality.
• tpsopt: average time spend to prune a node by optimality (in msec).
• nbdomi: number of nodes pruned by dominance.
• pctdomi: proportion (in %) of leaf nodes pruned by dominance.
• avgdomi: average time spend to prune a node by dominance (in msec).
• nbLB: number of lower bound set computed.
• avgfacets: average number of facets in the lower bound set (i.e. in \(\mathcal{L} + \mathbb{R}^p\)).
• avgNDf: average number of strictly non-dominated facets.
• pctavgNDf: proportion (in %) of facets that are strictly non-dominated.
• avgWNDf: average number of weekly non-dominated facets.
• pctavgWNDf: proportion (in %) of facets that are weekly non-dominated.
• maxfacets: maximal number of facets a lower bound set had in the tree.
• maxNDf: number of strictly non-dominated facets in the lower bound set with the maximal number of facets.
• pctmaxNDf: proportion (in %) of facets that are strictly non-dominated in the lower bound set with the maximal number of facets.
• maxWNDf: number of weekly non-dominated facets in the lower bound set with the maximal number of facets.
• pctmaxWNDf: proportion (in %) of facets that are weekly non-dominated in the lower bound set with the maximal number of facets.
• tpstotal: CPU time (in sec) used to solve the instance. 3600 if the instance is not solved.
• tpsLB: CPU time (in sec) used to compute lower bound sets.
• pcttpsLB: proportion (in %) of the total CPU time spend in the computation of lower bound sets.
• tpsdomi: CPU time (in sec) used to dominance test when the algorithm has to determine whether a node can be pruned by dominance or not.
• pcttpsdomi: proportion (in %) of the total CPU time spend in the dominance test when the algorithm has to determine whether a node can be pruned by dominance or not.
• tpsUB: CPU time (in sec) used to update the upper bound set.
• pcttpsUB: proportion (in %) of the total CPU time spend in updating the upper bound set.
• tpsnodesel: CPU time (in sec) used to choose the next node to develop.
• pcttpsnodesel: proportion (in %) of the total CPU time spend in choosing the next node to develop.
• tpsvarsel: CPU time (in sec) used to choose the variable to branch on.
• pcttpsvarsel: proportion (in %) of the total CPU time spend in choosing the variable to branch on.
• tpsOB: CPU time (in sec) used to create the sub-problems in the objective space, i.e. to compute objective branching. (/! it requires two different steps in total: computing the SLUBs but also do additional dominance test to determine the dominance status of each local upper bounds ! This number take into account the two steps.)
• pcttpsOB: proportion (in %) of the total CPU time spend in computing objective branching.
• tpsSLUB: CPU time (in sec) used to compute the super local upper bounds.
• pcttpsSLUB: proportion (in %) of the total CPU time spend in computing the super local upper bounds.
• tpsdomiLUB: CPU time (in sec) used to do the additionnal dominance tests to get the dominance status of EACH local upper bound.
• pcttpsdomiLUB: proportion (in %) of the total CPU time spend in doing the additionnal dominance tests on the local upper bounds.
• nbOB: number of nodes where two or more sub-problems are created in the objective space. When using the exact objective branching (OB = exact), it in particular shows how often it is actually possible to split the objective space with the definition of the sub-problems that we used (\(z(x) \leqq \bar{z}\), \(\bar{z} \in \mathbb{R}^p\)).
• pctnbOB: proportion (in %) of the nodes explored that where split in two or more sub-problems in the objective space.
• avgdepthOB: [relevant only if OB = exact] average depth of the nodes split in two or more sub-problems in the objective space.
• mindepthOB: [relevant only if OB = exact] minimal depth of the nodes split in two or more sub-problems in the objective space.
• maxdepthOB: [relevant only if OB = exact] maximal depth of the nodes split in two or more sub-problems in the objective space.
• avgnbpbOB: [relevant only if OB = exact] average number of sub-problems created in the objective space in the nodes split in two or more sub-problems in the objective space.
• maxnbpbOB: [relevant only if OB = exact] average number of sub-problems created in the objective space in the nodes split in two or more sub-problems in the objective space.
• ratioNDcoef: proportion (expressed as a number between 0 and 1) of objective coefficient vectors (here considered as a vector in \(\mathbb{R}^p\), one for each variable, defining the objective coefficient for all the objective for this variable) that are non-dominated (with respect to the other objective coefficient vectors).

For each instance, other statistics can be found in the details folder. We have:

• <instance>_coef.csv: each row correspond to a variable. The \(p\) first column represent the \(p\) objective coefficients for a given variable. The last column is 1 if the objective coefficient vector is not dominated by another one, 0 otherwise.
• <instance>_UB.csv: each row represent a \(y \in \mathcal{Y}_N\). The \(p\) first columns represent the values for the \(p\) objective functions. The other columns are redundant information with what comes later and can be ignored.
• <instances>_XE.csv: each row represent a \(y \in \mathcal{Y}_N\), sorted exactly in the same order as in <instance>_UB.csv. Each column represent the value of a variable, corresponding to the pre-image of the current \(y\).

For each run, statistics on the non-dominated points can be found in the folder UBrun. The names of the files are in the form <instance>_<nodesel>_<varsel>_<OB>_UB.csv, where <instance is the name of the instance, <nodesel> is the node selection strategy (see next section for the names), <varsel> is the variable selection strategy (see next section for the names) and <OB> is the objective branching strategy (-2 for OB = None, 1 for OB = cone, 2 for OB = exact). In this file, each row correspond to a \(y \in \mathcal{Y}_N\). The statistics are the following:

• the \(p\) first columns correspond the values of the objective functions.
• node: number of the node where this point has been discovered. The higher this number is, the later the point has been discovered.
• time: time (in sec) elapsed between the start of the algorithm and when this point has been found (for the first time).
• depth: depth of the node where this point has been found (for the first time).

3 Research questions

The first purpose of this study is to learn how some components of the branch and bound influences the behaviour of the algorithm it terms of computational time (expressed in seconds everywhere) and in term of number of nodes explored (i.e. how much nodes are developed in the branch and bound tree before the algorithm ends).

The branch and bound algorithm will always use the linear relaxation as lower bound set and the incumbent set as upper bound set. At each nodes, the extreme points of the lower bound set are checked for integrality and possibly added to the upper bound set. The components that will vary are:

• the node selection : in the multi-objective branch and bound literature, depth first strategies are (almost) always used and are considered as better strategies than breadth first. However, our conjecture is that if a problem with an “easy” single-objective version is solved, then many non-dominated points may be found in a node close to the root node, in the early stages of the tree. Hence, using a breadth first strategy may provide a better upper bound set earlier in the algorithm, as a larger number of points are expected to be found shallow in the tree while only a few points can be found at each node deep in the tree (1 maximum at a leaf node for example). However, it is not clear to see what is the actual impact. Hence, here comes the first research question : how does depth and breadth first strategies affects the behaviour of the algorithm ? (computational time, number of nodes explored)

• the variable selection : to the best of our knowledge, no extensive study for variable selection has been conducted in the literature. Sometimes, this component is even not mentioned. As it is not the main purpose of this study, only two rules that rely on the caracteristics of the lower bound set will be tested here.

  • mof : Most Often Fractional. The branching is operated on the variable that is the most often fractional among the extreme points of the lower bound set.

  • mfavg : Most Fractional in AVeraGe. The branching is operated on the variable such that its average value among the extreme points of the lower bound set is the most fractional, i.e. the closest to 0.5.

• the branching scheme : in a regular branch and bound, branching is operated (i.e. sub-problems are created) in the decision space. In the bi-objective case, it has been shown that creating additional sub-problems in the objective space (procedure called objective branching in this study) leads to better computational times. A new research question arises here : what is the impact of objective branching on a branch and bound algorithm for solving problems with three objectives ? In order to address that, three versions of the branch and bound will be tested (with the best node and variable selection previously identified for each problem configuration):

  • None : no objective branching is performed. Hence, this version is just a regular branch and bound.

  • exact : objective branching is performed using the algorithm from [master thesis paper].

  • unique cone : a unique sub-problem is created at each node. In this case, objective branching is applied on the nadir point of the local upper bounds dominated by the lower bound set. See [master thesis paper] for more details.

The second purpose of this study is to learn how the caracteristics of an instance can affect its difficulty. The difficulty will be here mesured by the size of the non-dominated set, and the computational time required to solve the instance. The computational time will be determined using the branch and bound algorithm previously described. Note that the complexity of an objective space search algorithm is positively correlated to the size of the non-dominated set as the more non-dominated there are, the more integer programs have to be solved.

The focus will be here on the objective function coefficients. The first research question here is: does the range of the objective function coefficient has an impact on the difficulty of the problem ?. In order to answer that, three different ranges will be tested:

• \([1,10]\) : a small range of values.
• \([1,1000]\) : a large range of values
• \([1000,2000]\) : a large range of values, but shifted to larger values.

For the facility location problems, two sets of costs (i.e. coefficients of objective function) can be identified: the assignment costs (\(c_{ij}\)) and the facility opening costs (\(f_j\)). It is reasonable to assume that these two sets of costs may not take their values in the same range. Let the assignment costs take their values in \([a,b]\), the generation of the facility opening costs will be divided into two categories of instances:

• facility location easy : \(f_j \in [b+a,b+b]\). It is called “easy” because it seems that having high facility opening costs makes the problem easier (see later in the study).
• facility location hard : \(f_j \in [0.1a,0.1b]\). It is called “hard” because it seems that having small facility opening costs makes the problem harded (see later in the study).

The second research question related to that topic is: does the method used to generate the coefficients of the objective function has an impact on the difficulty of the problem ?. Indeed, the usual procedure to generate objective function is to generate the coefficients randomly in a given range \([a,b]\). However, one could imagine other way to generate coefficient. Four methods will be studied here.

• random : the coefficient are generated randomly with a uniform distribution in the range \([a,b]\). For three objectives, random generated coefficients looks as follows.

You must enable Javascript to view this page properly.

• sphere down : the coefficients are generated on the lower part of a sphere (see next picture). Note that the sphere is adjusted such that the coefficients are in the range \([a,b]\), i.e. the sphere is not necessarily included in \([a,b]^p\).

You must enable Javascript to view this page properly.

• sphere up : the coefficients are generated on the upper part of a sphere (see next picture). Note that the sphere is adjusted such that the coefficients are in the range \([a,b]\), i.e. the sphere is not necessarily included in \([a,b]^p\).

You must enable Javascript to view this page properly.

• 2box : the coefficients are generated randomly but in two specific parts of \([a,b]^p\) (see next picture).

You must enable Javascript to view this page properly.

4 Preliminary tests CPU time

Here are tested different combinations of variable and node selection for the basic branch and bound. In the following :

• depth = depth first strategy for node selection. The last node created is the first explored.
• breadth = breadth first strategy for node selection. The first node created is the first explored.
• mof = Most Often Fractional strategy for variable selection. Branching is operated on the variable that is the most often fractional among the extreme points of the lower bound set.
• mfavg = Most Fractional in AVeraGe strategy for variable selection Branching is operated on the variable that is the most fractional (i.e. the closest to 0.5) in average among the extreme points of the lower bound set.

4.1 Random coefficient generation

The coefficient are generated using the random method.

4.1.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.1.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.1.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.1.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2 Sphere Down coefficient generation

The coefficient are generated using the spheredown method.

4.2.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.2.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.2.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.2.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3 Sphere Up coefficient generation

The coefficient are generated using the sphereup method.

4.3.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.3.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.3.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.3.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4 Two boxes coefficient generation

The coefficient are generated using the random method.

4.4.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.4.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.4.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.4.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

5 Study on the coefficients of the objective function

In this section, relations between |YN| and various characteristics of the coefficient of the objective function are studied.

5.1 Knapsack

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.2 Assignment

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.3 Facility location easy

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.4 Facility location hard

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

end